1. Field of the Invention
The invention disclosed and claimed herein pertains generally to a method and system for encrypting, transmitting and decrypting a message, wherein a private or secret key is furnished to both the sender and the receiver of the encrypted message. More particularly, the invention pertains to a method and apparatus of the above type, wherein modular arithmetic is used to achieve faster encryption, and to reduce the length or amount of transferred data.
2. Description of the Related Art
There is a continuing and ever increasing need for encryption algorithms that can be applied to computer related transmissions. These algorithms should be capable of providing encryption which is very hard to break or decode, that is, encryption which is non-deterministic polynomial-time (NP) hard. It is also desirable to minimize the amount of computing power that is required to implement an encryption algorithm.
As is well known by those of skill in the art, modular or modulo arithmetic is an arithmetic system in which integers return to zero, or “wrap around”, after a specified value, or modulus, has been reached. In the past, efforts to use modulo arithmetic in encryption algorithms have been significantly hampered, since such algorithms generally could not use non-prime numbers. As is also well known by those of skill in the art, a prime number is a positive integer that cannot be divided by any positive integer, except one and itself, without leaving a remainder. Accordingly, a non-prime number is a positive integer that can be divided by at least one other positive integer, in addition to one and itself, without leaving or producing a remainder.
Previous algorithms of the above type have not used non-prime numbers for at least two reasons. One reason is that encryption could result in zero. Another reason was that an encryption result was not necessarily unique, that is, it would be possible that a result would not be limited to a one to one mapping between an original message and the encrypted message.